// Copyright 2010 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package bsb

// A type, typically a collection, that satisfies sort.Compare can be
// binary searched by the routines in this package.  The methods require that the
// elements of the collection be enumerated by an integer index.
type Compare interface {
	Interface
	// Lt is true if v < p[i]
	Lt(key interface{}, i int) bool
	LtInt(key int, i int) bool
	// Gt is true if v >  p[i]
	Gt(key interface{}, i int) bool
	GtInt(key int, i int) bool
	// Cmp compares v with element at index i, returning -1, 0, or 1
	Cmp(key interface{}, i int) int
	CmpInt(key int, i int) int
}

func TAssertLtGt(key interface{}, data Compare) int {
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if data.Lt(key, mid) {
			hi = mid - 1
		} else if data.Gt(key, mid) {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

func TAssertCmp(key interface{}, data Compare) int {
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		cmp := data.Cmp(key, mid)
		switch {
		case cmp < 0:
			hi = mid - 1
		case cmp > 0:
			lo = mid + 1
		case cmp == 0:
			return mid
		}
	}
	return -1
}

func IntLtGt(key int, data Compare) int {
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if data.LtInt(key, mid) {
			hi = mid - 1
		} else if data.GtInt(key, mid) {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

func IntCmp(key int, data Compare) int {
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		cmp := data.CmpInt(key, mid)
		switch {
		case cmp < 0:
			hi = mid - 1
		case cmp > 0:
			lo = mid + 1
		case cmp == 0:
			return mid
		}
	}
	return -1
}

func Int1(key int, data IntArray) int {
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if key < data[mid] {
			hi = mid - 1
		} else if key > data[mid] {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

func Int2(key int, data IntArray) int {
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		x := data[mid]
		if key < x {
			hi = mid - 1
		} else if key > x {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

func Int3(key int, data IntArray) int {
	var x int
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		x = data[mid]
		if key < x {
			hi = mid - 1
		} else if key > x {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

func Int4(key int, data IntArray) int {
	var x, mid int
	lo := 0
	hi := data.Len() - 1
	for lo <= hi {
		mid = lo + (hi-lo)/2
		x = data[mid]
		if key < x {
			hi = mid - 1
		} else if key > x {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

func (p IntArray) Lt(key interface{}, i int) bool {
	return key.(int) < p[i]
}
func (p IntArray) Gt(key interface{}, i int) bool {
	return key.(int) > p[i]
}

func (p IntArray) LtInt(key int, i int) bool { return key < p[i] }
func (p IntArray) GtInt(key int, i int) bool { return key > p[i] }

func (p IntArray) Cmp(key interface{}, i int) int {
	x := key.(int)
	if x > p[i] {
		return 1
	} else if x < p[i] {
		return -1
	}
	return 0
}

func (p IntArray) CmpInt(x int, i int) int {
	if x > p[i] {
		return 1
	} else if x < p[i] {
		return -1
	}
	return 0
}
